#define _CRT_SECURE_NO_WARNINGS 1


#include<iostream>

using namespace std;

template<class T>
struct AVLTreeNode
{
	AVLTreeNode<T>* _left;
	AVLTreeNode<T>* _right;
	AVLTreeNode<T>* _parent;
	int _bf;
	T data;

	AVLTreeNode(const T& data = T())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_data(data)
	{ }
};

template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	bool insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (data > cur->data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (data < cur->data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (cur->data > parent->data)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else
			{

			}
		}

		return true;
	}

private:
	Node* _root = nullptr;
};